package main

import "fmt"

// 分析斐波那契数列递推公式递归版本的问题，试着为该函数提供一个Cache，使其计算效率提升

// 使用一个 map 来缓存已经计算过的斐波那契数值
var cache = make(map[int]int)

func fibonacci(n int) int {
	// 如果缓存中有值，则直接返回
	if val, found := cache[n]; found {
		return val
	}

	// 递归计算斐波那契数值
	if n <= 1 {
		cache[n] = n // 0 或 1 直接存储结果
	} else {
		cache[n] = fibonacci(n-1) + fibonacci(n-2)
	}

	return cache[n]
}

func main() {
	// 测试
	fmt.Println("Fibonacci(10):", fibonacci(10)) // 应该输出55
}
